package com.ry.day1129;

import java.util.Arrays;

public class LC92 {

    static class Solution {
        /**
         * @param m: An integer m denotes the size of a backpack
         * @param a: Given n items with size A[i]
         * @return: The maximum size
         */
        public int backPack(int m, int[] a) {
            //return cache(m,a); //傻缓存
            return dp(m,a); //动态规划
        }

        public int dp(int m,int[] a){
            int n= a.length;
            int[][] dp = new int[n+1][m+1];
            for (int idx = n-1; idx >=0 ; idx--) {
                for (int rest = 0; rest <=m ; rest++) {
                    int p1 = dp[idx+1][rest];
                    int p2 =0;
                    int next = rest-a[idx] <0?-1: dp[idx+1][rest-a[idx]];
                    if(next!=-1){
                        p2 = a[idx]+next;
                    }

                    dp[idx][rest] = Math.max(p1,p2);
                }
            }
            return dp[0][m];
        }
        public int cache(int m,int[] a){
            int n = a.length;
            int[][] dp = new int[n+1][m+1];
            for (int i = 0; i <=n ; i++) {
                Arrays.fill(dp[i],-1);
            }
            return f1(a,0,m,dp);
        }
        public int f1(int[] arr,int idx,int bagsize,int[][] dp){
            if(bagsize<0) return -1;
            if(idx == arr.length) return 0;
            if(dp[idx][bagsize]!=-1){
                return dp[idx][bagsize];
            }

            int p1 = f1(arr,idx+1,bagsize,dp);//不要当前的货物
            int p2 =0;
            int next = f1(arr,idx+1,bagsize-arr[idx],dp);
            if(next!=-1){
                p2=arr[idx]+next;
            }

            int ans = Math.max(p1,p2);
            dp[idx][bagsize] = ans;
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.backPack(10,new int[]{3,4,8,5}));
    }
}
